def solve_maze(maze, coin_value=50, trap_penalty=-30, boss_penalty=-10, locker_penalty=-70):
    # 找到起点和终点
    start_pos = None
    exit_pos = None
    for i in range(len(maze)):
        for j in range(len(maze[0])):
            if maze[i][j] == 'S':
                start_pos = (i, j)
            elif maze[i][j] == 'E':
                exit_pos = (i, j)
            if start_pos and exit_pos:
                break
        if start_pos and exit_pos:
            break
    
    # 价值定义
    values = {'G': coin_value, 'T': trap_penalty, 'B': boss_penalty, 'L': locker_penalty, ' ': 0, '#': float('-inf')}
    
    # 用于计算性价比时的价值（B和L代价为0）
    cost_values = {'G': coin_value, 'T': trap_penalty, 'B': 0, 'L': 0, ' ': 0, 'E': -1, '#': float('-inf')}
    
    from collections import deque
    import random
    
    def get_3x3_vision(pos):
        """获取3x3视野内的信息"""
        r, c = pos
        vision = []
        for dr in [-1, 0, 1]:
            for dc in [-1, 0, 1]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < len(maze) and 0 <= nc < len(maze[0]):
                    vision.append(((nr, nc), maze[nr][nc]))
                else:
                    vision.append(((nr, nc), '#'))
        return vision
    
    def bfs_path(start, target, visited_global):
        """BFS计算从start到target的最短路径"""
        if start == target:
            return [start]
        
        queue = deque([(start, [start])])
        visited_local = {start}
        
        while queue:
            pos, path = queue.popleft()
            r, c = pos
            
            for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
                nr, nc = r + dr, c + dc
                if (0 <= nr < len(maze) and 0 <= nc < len(maze[0]) and 
                    (nr, nc) not in visited_local and 
                    maze[nr][nc] != '#'):
                    
                    new_path = path + [(nr, nc)]
                    if (nr, nc) == target:
                        return new_path
                    
                    queue.append(((nr, nc), new_path))
                    visited_local.add((nr, nc))
        
        return None
    
    def calculate_cost_benefit(pos, vision, visited_global):
        """计算视野内各点的性价比"""
        candidates = []
        current_r, current_c = pos
        
        for (r, c), cell in vision:
            # 只考虑3x3范围内的点
            if abs(r - current_r) <= 1 and abs(c - current_c) <= 1:
                if ((r, c) not in visited_global and 
                    cell != '#' and 
                    (r, c) != pos):
                    
                    path = bfs_path(pos, (r, c), visited_global)
                    if path and len(path) > 1:
                        distance = len(path) - 1
                        value = cost_values.get(cell, 0)
                        cost_benefit = value / distance if distance > 0 else value
                        candidates.append(((r, c), cell, path, cost_benefit, value))
        
        return candidates
    
    def dfs_explore(current_pos, total_value):
        """DFS探索，优先选择性价比最高的路径"""
        nonlocal result_path, visited
        print(f"当前位置: {current_pos} 总价值: {total_value}")
        visited.add(current_pos)
        result_path.append(current_pos)
        
        # 获取当前视野
        vision = get_3x3_vision(current_pos)
        
        # 计算候选位置的性价比
        candidates = calculate_cost_benefit(current_pos, vision, visited)
        candidates = [c for c in candidates if (maze[c[0][0]][c[0][1]] == 'E' or c[3] >= 0) and len(c[2]) <= 3 and c[0] not in visited]
        candidates.sort(key=lambda x: (x[3], -len(x[2])), reverse=True)
        
        print(f"候选位置:")
        for candidate in candidates:
            print(f"位置: {candidate[0]}, 价值: {candidate[4]}, 路径: {candidate[2]}")
        print('--------------------------------')
        if not candidates:
            return 
        
        # 按性价比排序
        
        for candidate in candidates:
            if candidate[0] not in visited:
                target_pos, cell, move_path, cost_benefit, cell_value = candidate
                if move_path[1] not in visited:
                    dfs_explore(move_path[1], total_value + cost_values.get(move_path[1], 0))
                    result_path.append(current_pos)
        
        return 
    # 预处理
    prepath = bfs_path(start_pos, exit_pos, set())
    change_pos = set()
    
    for pos in prepath:
        if maze[pos[0]][pos[1]] == 'T':
            maze[pos[0]][pos[1]] = ' '
            change_pos.add(pos)
    
    
    # 收集资源
    visited = set()
    result_path = []
    path = []
    print("开始第一次DFS探索...")
    dfs_explore(start_pos, 0)
    
    path_end_pos = -1
    for i in range(len(result_path)):
        if maze[result_path[i][0]][result_path[i][1]] == 'E':
            path_end_pos = i
            break
        
    final_path = result_path[:path_end_pos+1]
    print(f"路径长度: {len(final_path)}")

    
    # 第二次DFS：前往出口
    # print("\n开始第二次DFS，前往出口...")
    # current_position = first_path[-1] if first_path else start_pos
    
    # # 使用BFS找到从当前位置到出口的路径
    # exit_path = bfs_path(current_position, exit_pos, set())
    
    # if exit_path:
    #     # 添加到出口的路径（跳过起点避免重复）
    #     final_path = first_path + exit_path[1:]
    #     print(f"成功找到出口！")
    #     print(f"到出口路径长度: {len(exit_path)-1}")
    # else:
    #     final_path = first_path
    #     print("无法到达出口！")
    
    print(f"\n总路径长度: {len(final_path)}")
    
    print(final_path)
    for pos in change_pos:
        maze[pos[0]][pos[1]] = 'T'
    
    collect_coin = set()
    collect_trap = set()
    collect_boss = set()
    collect_locker = set()
    for pos in final_path:
        if maze[pos[0]][pos[1]] == 'G':
            collect_coin.add(pos)
        elif maze[pos[0]][pos[1]] == 'T':
            collect_trap.add(pos)
        elif maze[pos[0]][pos[1]] == 'B':
            collect_boss.add(pos)
        elif maze[pos[0]][pos[1]] == 'L':
            collect_locker.add(pos)
    finalscore = len(collect_coin) * coin_value + len(collect_trap) * trap_penalty + len(collect_boss) * boss_penalty + len(collect_locker) * locker_penalty
    print(f"总得分: {finalscore}")
    return final_path, finalscore

# 执行求解
# final_path = solve_maze()
# print(final_path)